package cn.edu.xjtu.work.fib;

import java.util.ArrayList;
import java.util.List;

/**
 * 509. 斐波那契数
 * 
 * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
 * 
 * 也就是F(0)= 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 * 
 * 给你 n ，请计算 F(n) 。
 */
public class Solution {

  /**
   * 动态规划
   * 
   * @param n
   * @return
   */
  public int fib(int n) {
    List<Integer> list = new ArrayList<>(n);
    list.add(0);
    list.add(1);
    for (int i = 2; i <= n; i++) {
      list.add(list.get(i - 1) + list.get(i - 2));
    }
    return list.get(n);
  }

  /**
   * 递归
   * 
   * @return
   */
  public int fib1(int n) {
    if (n == 0 || n == 1) {
      return n;
    }
    return fib1(n - 1) + fib1(n - 2);
  }

}
